The present invention relates to programmable logic devices and, more particularly, to a routing architecture for such devices.
Various programmable logic architectures are known, including, for example, programmable logic devices (xe2x80x9cPLDsxe2x80x9d), programmable logic arrays (xe2x80x9cPLAsxe2x80x9d), complex programmable logic devices (xe2x80x9cCPLDsxe2x80x9d), field programmable gate arrays (xe2x80x9cFPGAsxe2x80x9d) and programmable array logic (xe2x80x9cPALxe2x80x9d). Although there are differences between these various architectures, each of the architectures typically includes a set of input conductors directly coupled as inputs to an array of logic gates (e.g., a product term array made up of logical AND gates), the outputs of which, in turn, act as inputs to another portion of the logic device.
For complex programmable logic devices, wherein the number of input conductors and the number of logical AND gates to which they connect are both quite large compared with other programmable logic architectures, maintaining full connectability of the product term array for each input conductor becomes impractical for several reasons. First, to maintain full connectability the size of the input field of each logical AND gate in the product term array must increase for each input conductor that is added. Second, the addition of a single input conductor requires the addition of a number of programmable elements equal to the total number of logical AND gates, one for each logical AND gate. Third, the total number of conductors that are routed from the programmable elements to the logical AND gates increases as the number of programmable elements increases. All of these consequences of attempting to maintain full connectability for CPLDs results in a large increase in die space for the product term array without a proportionate increase in functionality over a less complex PLD.
One solution to this dilemma is to interpose a connection circuit that is not fully connectable between the set of input conductors and the product term array of a logic block, wherein the inputs of the connection circuit are coupled to the input conductors of the CPLD and the outputs of the connection circuit are coupled to the inputs of the product term array of a logic block. One such connection circuit is associated with each CPLD logic block, or multiple numbers of logic blocks, and provides a unique connection between CPLD inputs and the product term array inputs of the associated logic block. Typically, this connection circuit allows only a subset of the CPLD inputs to be connected to the product term array inputs.
Early CPLDs implemented this connection circuit as a programmable, fully populated cross-point matrix similar to that used in a fully programmable product term array. Each input conductor of the connection circuit is connected to a number of programmable elements equal to the number of output conductors of the connection circuit, wherein in each programmable element is capable of providing a unique connection between the input conductor and one of the output conductors. Such a connection circuit guarantees a route for every possible combination of input signals up to the total number of output conductors of the front end connection, regardless of the ordering of the combination. The fully populated cross-point matrix may thus be said to have xe2x80x9cfull connectability,xe2x80x9d wherein the term connectability denotes the ability of the connection circuit to connect an input conductor of the connection circuit to the output conductors of the connection circuit. A fully connectable connection circuit is one that can connect every input conductor to every output conductor.
Such early approaches were rather inefficient. For example, the number of programmable elements required for each connection circuit is equal to the total number of CPLD input conductors, nin, multiplied by the number of output conductors, nout, for the connection circuit, wherein nout is typically equal to the number of input terms for the product term array of the associated logic block. As a CPLD typically implements two or more connection circuits, this approach requires large amounts of die area.
Further, of the nin programmable elements connected to any one of the nout output conductors, only one of the programmable elements is ever programmed, regardless of the input signal selected for routing through the connection circuit. Otherwise, two or more input signals may be shorted together. Thus, the maximum number of programmable elements that are ever used to route any combination of input signals through a fully populated cross point matrix is nout. This means that the maximum percentage of programmable elements that are used for any one connection circuit is equal to 0.1/nin. Therefore, the amount of die space required to implement the fully connectable cross-point matrix is excessive in light of the under utilization of the programmable elements. The inefficiency of such early approaches is only emphasized when the number nin of CPLD inputs increases.
An alternative connection circuit provides full connectability while requiring less xe2x80x9cconnectivityxe2x80x9d than the fully populated cross-point matrix. The term connectivity refers to the total number of programmable elements provided by a connection circuit. This alternative connection circuit uses a number nout of nin:1 multiplexers, wherein the output of each multiplexer is connected to an output conductor of the connection circuit. As each multiplexer requires only log nin/log 2 programmable elements, the total number of programmable elements (the connectivity) for a fully connectable multiplexer array is reduced to nout multiplied by log nin/log 2. This results in some savings of die space over the fully connectable cross-point matrix, however, the die space requirements are still excessive, especially when the number nout of CPLD inputs increases.
To further reduce the amount of semiconductor die area needed for a connection circuit, the connectivity of the connection circuit may be further reduced by providing even fewer programmable elements. This reduction in connectivity results in connection circuits that are not fully connectable, which means that every input conductor of the connection circuit cannot be connected to every output conductor of the connection circuit. The level of connectability for a connection circuit is related to the level of xe2x80x9croutabilityxe2x80x9d of the connection circuit. Here, the term routability denotes the probability that the connection circuit can provide a route (or signal path) for any given combination of input signals from the input conductors to the output conductors of the connection circuit. The routability of the connection circuit tends to increase with the connectability of the connection circuit.
Because every input conductor can no longer be connected to an output conductor, the number of routes through the connection circuit for a particular combination of input signals may be reduced when compared to the fully connectable connection circuits. So long as the connection circuit provides at least one route for every combination of input signals, the connection circuit is fully routable or 100% routable. If no route can be provided for a particular combination of input signals, the connection circuit is not fully routable. Fully connectable connection circuits have maximum routability as they provide a route for every permutation of input signals.
Connectivity for a multiplexer array is reduced by reducing the width of the input field for each multiplexer such that the number of input conductors that are coupled to each multiplexer is less than the total number of input conductors for the connection circuit. So long as each input signal is provided with at least one chance to route, that is, each input conductor is connected to at least one multiplexer, a successful routing for a particular logic function can be achieved regardless of the routability of the connection circuit. For such a constrained multiplexer, providing a route for a particular logic function may require a carefully chosen pin assignment for the CPLD such that the desired combination of input signals are connected to input conductors that have a route through the connection circuit to the output conductors. If the particular logic function is changed at a later time, the same pin assignment may not be able to provide a route for the selected combination of input signals for the altered logic function.
To better ensure that pin assignments do not have to be altered when a logic function is altered, the routability of the connection circuit should be maximized. As described above, a greater level of connectability for a connection circuit tends to result in a greater level of routability for the connection circuit. However, a greater level of connectability requires a greater level of connectivity, and more die area is consumed, which typically results in higher device costs and slower device speeds. The challenge then is to find the optimum balance between connectivity, connectability and routability for connection circuit.
FIG. 1 shows a conventional CPLD 100 which includes a connection circuit implemented as a programmable interconnect matrix (xe2x80x9cPIMxe2x80x9d) 110 and eight logic blocks 120. Although eight logic blocks 120 are shown, as few as two logic blocks may be used in a conventional CPLD such as CPLD 100. CPLD 100 has a total of 262 inputs, each of which is connected to the PIM 110. The PIM 110 is capable of providing each logic block 120 with its own set of input terms by independently selecting as many as 36 of the possible 262 input signal as input terms for each logic block 120. As shown, the logical compliments for each of the 36 signals output by the PIM 110 are also provided to each logic block 120. Thus, each logic block receives as many as 72 input terms from the PIM 110.
The PIM 110 includes a number of programmable elements for controlling an array of multiplexers to reduce the total number of programmable elements required. The programmable elements may be volatile memory elements such as static random access memory (xe2x80x9cSRAMxe2x80x9d) cells, non-volatile memory elements such as electrically erasable programmable read only memory (xe2x80x9cEEPROMxe2x80x9d) cells, flash memory cells or fuses. Alternatively, the programmable elements of PIM 110 may be implemented to control a matrix of cross point switches, however, this increases the total number of programmable elements required to make the same number of connections. Whether the connections between input conductors and output conductors are provided by a cross-point switch matrix or by an array of multiplexers, each output conductor can be connected to a maximum of one input conductor. Thus, both forms of connection perform a multiplexing function in the sense that both forms of connection provide for the selection of one input conductor from a set of many input conductors. Therefore, as used herein, the term multiplexer should be understood to encompass any circuit that performs a multiplexing function, regardless of the number of programmable elements required to control that circuit.
The 262 inputs to the PIM 110 include 128 feedback signals, 128 input signals, and 6 dedicated input signals. Four clock signals may be provided directly to each of the logic blocks 120. Sixteen feedback signals are provided by each logic block 120. Each logic block 120 is programmed to perform selected logic functions using sub-combinations of the 72 input terms provided by the PIM 110. Each logic block 120 has 16 input/output (xe2x80x9cI/Oxe2x80x9d) pins 130, which may be used either as inputs to the PIM 110 or outputs of CPLD 100.
Conceptually, CPLD 100 may be regarded as a PIM coupled in series with 8 PLDs coupled in parallel, wherein each logic block 120 corresponds to a single PLD. Intermediate stages and the outputs of each of the 8 PLDs are fed back as inputs to the PIM. Depending on the particular set of input signals routed to the output of the PIM and the programmed logic functions for each logic block 120, the 8 PLDs may, in fact, act as two or more PLDs coupled in series with each other. CPLD 100 thus provides a highly versatile logic device which may be implemented on a single semiconductor die.
FIG. 2 shows portions of CPLD 100 in greater detail. Specifically, a logic block 120 is shown as including a product term array 210, a product term allocator 215, macrocells 220 and I/O cells 225. The product term array may be a fully programmable logical AND array. The product term allocator 215 allocates product terms from the product term array 210 to a number of macrocells (e.g., 16) 220. The product term allocator 215 xe2x80x9csteersxe2x80x9d product terms to the macrocells 220 as needed. For example, if one macrocell 220 requires 10 product terms while another requires only three product terms, the product term allocator 215 steers 10 product terms to the first macrocell and three product terms to the latter. Up to 16 product terms can be steered to any one macrocell.
The outputs for each of the 16 macrocells 220 are fed back to the PIM 110 as input signals. This specific architecture of the macrocells 220 may be any appropriate architecture and may include clocked registers and buffers. The 16 outputs of the macro cells 220 are also fed to 16 I/O cells 225. The output signals of the 16 I/O cells 225 are fed back as input signals to the PIM 110 and also provided to I/O pins 130.
FIG. 3 shows an alternative representation of CPLD 100. In this representation, CPLD 100 is divided into N slices, where each slice includes a pair of logic blocks 120 and an associated portion of the PIM 1101-100N. In terms of die layout, each slice 3001-300N of CPLD 100 may be considered a building block for the overall CPLD 100. Interconnection between the PIM slices 1101-110N may be provided by other connection circuits which are fully connectable or less than fully connectable. As shown, each logic block 120 of a slice 300 receives xe2x80x9cixe2x80x9d inputs from a corresponding PIM slice 1101-110N. Each of the i inputs is selected from a pool of global inputs and logic block local feedbacks through the PIM 110. The number of inputs and the number of outputs possessed by the PIM 110 determine the number of possible combinations of input signals that can be selected for output by the PIM. The level of routability of the PIM 110 determines how many of the possible combinations can actually be routed by the PIM. To be fully routable, the PIM must provide a route to the outputs of the PIM for each possible combination of the input signals.
As shown in FIG. 4, PIM 110 is a multiplexer-based interconnect with an M-input multiplexer 402 for each input to a logic block 120. Thus, for i inputs to an individual logic block 120, a PIM slice 1101-110N must include i multiplexers 402. For two logic blocks 120 per slice, this means that 2i multiplexers 402 per PIM slice must be provided. Associated with each multiplexer 402 are configuration memory bits 404 which are used to select which of the M inputs for each multiplexer 402 will be provided as the output of that multiplexer.
As shown in FIG. 5, each M:1 multiplexer 402 uses M switching elements 502. The switching elements may be pass gates (i.e., transistors). Thus, there are M transistors for each input (of i inputs) to a logic block 120. If each i-input logic block 120 uses i multiplexers 402, there are Mxc3x97i transistors for that logic block and 2Mxc3x97i transistors for a pair of logic blocks 120 per slice 300. In total, then, the N slices 300 of CPLD 100 will require 2xc3x97Nxc3x97Mxc3x97i transistors or other switching elements to implement PIM 110. In addition, each multiplexer 402 typically requires Mxc3x97i configuration bits 404 to select an appropriate input signal as an output. Thus, a total of 2xc3x97Nxc3x97Mxc3x97i configuration bits will be required for PIM 110.
The number of switching elements and configuration bits to implement PIM 110 is thus quite large. It would be desirable to achieve a similar routability as provided by PIM 110 while utilizing fewer selection elements and/or configuration bits.
The present invention provides, in one embodiment, a routing architecture which includes a plurality of switching elements grouped so as to provide one or more outputs for a plurality of inputs, wherein the grouping represents a hierarchy of selection levels. The routing architecture may be configured such that at each of the selection levels fewer outputs are provided than inputs are received. The selection levels may be implemented using one or more multiplexers at each of the levels.
In a further embodiment, the present invention provides a programmable logic device which includes a routing architecture having a plurality of switching elements grouped so as to provide one or more outputs for a plurality of inputs, the grouping representing a hierarchy of selection levels. Such a programmable logic device may also include a number of logic blocks, wherein each of the logic blocks is coupled to receive at least one of the outputs of the routing architecture. Further still, the programmable logic device may be configured so that a subset of the plurality of inputs to the routing architecture are provided by one or more of the logic blocks. The switching elements of the routing architecture may include a number of interconnected primary and secondary multiplexers. The interconnection of the primary and secondary multiplexers may, in such an embodiment, define the hierarchy of the selection levels. Each secondary multiplexer may have a number of corresponding primary multiplexers equal to the number of inputs of that secondary multiplexer.
In another embodiment of the present invention, a programmable interconnect matrix includes a plurality of multiplexers arranged in a multi-level interconnection scheme so as to provide a first number of output signals from a second number of input signals. Such a programmable interconnect matrix may be configured such that the plurality of multiplexers are arranged as primary multiplexers and secondary multiplexers, the primary multiplexers being configured to receive the input signals and the secondary multiplexers being configured to provide the output signals. Each secondary multiplexer may be coupled to an equal number of primary multiplexers.
In still a further embodiment of the present invention, a programmable logic device is provided which includes a programmable interconnect matrix having a plurality of multiplexers arranged in a multilevel interconnection scheme so as to provide a first number of output signals from a second number of input signals. Such a programmable logic device may also include a number of logic blocks, each coupled to receive one or more of the output signals from the programmable interconnect matrix. The plurality of multiplexers may include a number of primary multiplexers and a number of secondary multiplexers, wherein each of the secondary multiplexers is associated with a subset of the number of primary multiplexers and each is further configured to provide one of the number of output signals. The subset of primary multiplexers may further be selected in such a way that the logic block that receives the output signal is also the primary contributor of input signals to the subset of primary multiplexers. This would result in the logic block taking advantage of the principle of locality, i.e., where the signals produced by a logic block are more likely to be used by that logic block than signals produced by another logic block. The programmable logic device may be further configured such that at least one of the input signals is provided by one of the logic blocks.
In still a further embodiment of the present invention, a programmable interconnect matrix having a plurality of routing elements arranged in an hierarchical routing scheme is provided. The number of routing elements is equal to M+Lxc3x97S for the case where the number of levels equals two, and where M represents the number of inputs to the programmable interconnect matrix, L represents the number of groups of outputs from the programmable interconnect matrix and S represents the number of routing elements at the lowest level of the hierarchical routing scheme. The programmable interconnect matrix may be embodied within a programmable logic device which also includes a number of logic blocks. Each of the logic blocks may be coupled to receive one of the groups of outputs from the programmable interconnect matrix. Further, at least one of the logic blocks may be configured to provide at least one of the inputs to the programmable interconnect matrix. In addition, or alternatively, the programmable logic device may include a number of such programmable interconnect matrices, each having an associated number of logic blocks.